class Solution(object):
    def repeatedStringMatch(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: int
        """
        m = len(a)
        n = len(b)
        pi = [0] * m
        j = 0
        if b in a:
            return 1
        for i in range(1, m):
            while j > 0 and a[i] != a[j]:
                j = pi[j - 1]
            if a[i] == a[j]:
                j += 1
            pi[i] = j
        count = 0
        start = -1
        j = 0
        for i in range(n):
            while j > 0 and b[i] != a[j]:
                j = pi[j - 1]
            if b[i] == a[j]:
                j += 1
            if j == m:
                count += 1
                start = i - j + 1
                j = 0
                end = i + 1
                break
        if count > 0:
            if start > 0:
                if b[:start] in a:
                    count += 1
                else:
                    return -1
            for i in range(end, n):
                if b[i] == a[j]:
                    j += 1
                    if j == m:
                        count += 1
                        j = 0
                else:
                    return -1
            if j > 0:
                count += 1
            return count
        if j > 0:
            if j == n:
                return 1
            else:
                if n - j < m:
                    if b[:-j] == a[j - n:]:
                        return 2
                    else:
                        return -1
                else:
                    return -1
        else:
            return -1





data = Solution()
# a = "abcd"
# b = "cdab"
# print(data.repeatedStringMatch(a, b))
# a = "abaabaa"
# b = "abaababaab"
# print(data.repeatedStringMatch(a, b))
# a = "aaaaaaaaaaaaaaaaaaaaaab"
# b = "ba"
# print(data.repeatedStringMatch(a, b))
a = "axaxaya"
b = "axaya"
print(data.repeatedStringMatch(a, b))


